import functools


class Solution(object):
    def ways(self, pizza, k):
        m = len(pizza)
        n = len(pizza[0])
        k = k - 1
        @functools.cache
        def find_apples(i, j):
            now_val = int(pizza[i][j] == 'A')
            if i < 0 or j < 0:
                return 0
            if i == 0:
                if j == 0:
                    return now_val
                else:
                    return find_apples(i, j - 1) + now_val
            else:
                if j == 0:
                    return find_apples(i - 1, j) + now_val
                else:
                    return find_apples(i - 1, j) + find_apples(i, j - 1) - find_apples(i - 1, j - 1) + now_val

        @functools.cache
        def dfs(i, j, t):
            apples = find_apples(m - 1, n - 1) - find_apples(i - 1, n - 1) - find_apples(m - 1, j - 1) + find_apples(i - 1, j - 1)
            if apples == 0:
                return 0
            if t == k:
                return 1
            ans = 0
            if j < n - 1:
                for u in range(j, n - 1):
                    qie_apples = find_apples(m - 1, u) - find_apples(m - 1, j - 1) - find_apples(i - 1, u) + find_apples(i - 1, j - 1)
                    if qie_apples:
                        ans += dfs(i, u + 1, t + 1)
            if i < m - 1:
                for u in range(i, m - 1):
                    qie_apples = find_apples(u, n - 1) - find_apples(i - 1, n - 1) - find_apples(u, j - 1) + find_apples(i - 1, j - 1)
                    if qie_apples:
                        ans += dfs(u + 1, j, t + 1)
            return ans

        return dfs(0, 0, 0)



data = Solution()
pizza = ["A..", "AAA", "..."]
k = 3
print(data.ways(pizza, k))
